#pragma comment(linker, "/STACK:10000000")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>
#include <cstdio>
#include <cassert>
#include <string>
#include <cstring>
#define ldb long double
#define ll long long
#define fi first
#define se second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define fill(a, c) memset(a, c, sizeof(a))
#define sqr(a) ((a) * (a))
#define nextLine() {int c = 0; while((c = getchar()) != 10 && c != EOF);}
#define getBit(mask, k) (((mask) / pw[k]) % pw[1])
#define setBit(mask, k, l) (((mask) / pw[k + 1] * pw[1] + (l)) * pw[k] + ((mask) % pw[k]))
#define debug(a) cerr << #a << " = " << (a) << " ";
#define debugl(a) cerr << #a << " = " << (a) << "\n";
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define ff first
#define ss second 
const ldb eps = 1e-9;
const int inf = 1 << 28;
const ldb pi = fabsl(atan2l(0.0, -1.0));
using namespace std;


string s, t;

void solve();

void load()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> s >> t;
		solve();
	}
}

int dp[123];
int dp2[52][52][28];

inline bool match(int init, int state, int end)
{
	if (state == 26) return init == end;
	else return state + 'a' == end;
}

int g(int l, int r, int ch)
{
	if (l > r) return 0;
	if (dp2[l][r][ch] != -1) return dp2[l][r][ch];
	if (match(s[l], ch, t[l]))
	{
		dp2[l][r][ch] = g(l + 1, r, ch);
	//	cerr << l << " " << r << " " << ch << " :  " << dp2[l][r][ch] << "\n";
		return dp2[l][r][ch];
	}
	if (match(s[r], ch, t[r]))
	{
		dp2[l][r][ch] = g(l, r - 1, ch);
	//	cerr << l << " " << r << " " << ch << " :  " << dp2[l][r][ch] << "\n";
		return dp2[l][r][ch];
	}
	dp2[l][r][ch] = inf;
	int up = r - l + 1;
	if (ch < 26) up--;
	if (ch < 26)
	{
		dp2[l][r][ch] = min(dp2[l][r][ch], g(l, r, t[l] - 'a') + 1);
		dp2[l][r][ch] = min(dp2[l][r][ch], g(l, r, t[r] - 'a') + 1);
	}
	for (int k = 1; k <= up; k++)
	{
		dp2[l][r][ch] = min(dp2[l][r][ch], g(l, l + k - 1, t[l] - 'a') + g(l + k, r, ch) + 1);
	}
//	cerr << l << " " << r << " " << ch << " :  " << dp2[l][r][ch] << "\n";
	return dp2[l][r][ch];
}

int f(int i)
{
	if (i == s.size()) return 0;
	if (dp[i] != -1) return dp[i];
	dp[i] = inf;
	for (int j = 1; j <= (int)s.size() - i; j++)
	{
		dp[i] = min(dp[i], g(i, i + j - 1, 26) + f(i + j));
	}
//	cerr << i << " " << f(i) << "\n";
	return dp[i];
}

void solve()
{
	memset(dp, -1, sizeof dp);
	memset(dp2, -1, sizeof dp2);
	cout << f(0) << "\n";
}

#define file "letter"
int main()
{
	freopen(file".in", "rt", stdin);
	freopen(file".out", "wt", stdout);
	load();
	return 0;
}

